Multiple processes running on multi-processing systems may access “shared resources.” Some of these shared resources may be accessed by only one process at a time, while others may be accessed concurrently by multiple processes. Consequently, “synchronization mechanisms” have been developed to control access by multiple processes to shared resources. The synchronization mechanism grants locks to processes. Locks grant to holders of the locks the right to access a particular resource in a particular way. Once a lock is granted to a process, the process holds or owns the lock until the lock is relinquished, revoked, or otherwise terminated. Locks are represented by data structures such as semaphores, read/write latches, and condition variables. There are many types of locks. Some types of locks allow shared resources to be shared by many processes concurrently (e.g. shared read lock), while other types of locks prevent any type of lock from being granted on the same resource (exclusive write lock).
The entity responsible for granting locks is referred to herein as a lock manager. In a single node multi-processing system, a lock manager is typically a software component executed and invoked by processes on the node accessing a shared resource.
In contrast to a single node system, a multi-node system consists of network of computing devices or “nodes, each of which may be a multi-processing system. Each of the nodes can access a set of shared resources. Multi-node systems use synchronization mechanisms, referred to as global synchronization mechanisms, to control access to the set of shared resources by nodes in the multi-node system.
A global lock mechanism includes a global lock manager that is responsible for issuing locks to processes on the multi-node system. In order for a node to access a shared resource, it is granted a “global lock” by a global lock manager. A global lock is a lock that can be granted by a global lock manager on a node in a multi-node system to one or more processes on another node to coordinate access to the shared resources among the processes executing on any node in a multi-node system.
One type of global lock manager, a central global lock manager, is responsible for issuing locks for all shared resources in a multi-node system. Another type of global lock manager, a distributed lock manager, is comprised of local lock managers, with one or more of the local lock managers running on each node in a multi-node system. Each lock manager is responsible for coordinating the global locks that are needed to access a subset of shared resources.
Nodes are described herein as performing actions and as being the object of actions. However, this is just a convenient way of expressing that one or more processes on a node are performing an action or is the object of an action. For example, a node accessing a shared resource or granting, holding, or being issued a lock is just a convenient way of expressing that a process on the node is accessing a shared resource or granting, holding, or being issued a lock.
In a distributed lock manager, a local lock manager residing on a node issues global locks to both processes on other nodes and to processes running on the same node as the local lock manager. A local lock manager is referred to as the local lock manager with respect to the node on which it resides; the node and a process running on the node are referred to as a local process and local node with respect to the local lock manager. In addition to a local lock manager on a node issuing global locks, a node in a multi-node system may issue local locks to local processes. Local locks are granted by a node only to local processes running on the node. In fact, in some distributed lock management systems, a local lock manager must obtain a local lock to a shared resource before obtaining a global lock. Local locks are used for exactly the same resources as the global locks. Only the scope of the locking is different. The local locks are used to synchronize access to shared resource among local processes in the node whereas global locks are used to synchronize access to the same shared resource among processes running on separate nodes. Examples of local locks include operating system locks on such resources as files or portions of memory.
Some local lock managers may obtain a global lock for a shared resource on behalf of one or more local processes. The local lock manager then issues local locks to the local processes to coordinate access among the local processes to the shared resource.
Global locks are more expensive than acquiring only local locks. Usually, local locks are issued in conjunction with global locks. Thus, issuing global locks entails executing instructions and creating data structures for both local locks and global locks. Even more, acquiring a global lock may entail inter-node communication in the form of messages transmitted between a local lock manager on one node and processes and/or a local lock manager on another node. Hence, techniques are needed to reduce the cost of acquiring global locks.
One technique to reduce the cost of acquiring global locks is to use a “mastering technique” that assigns a master node to a subset of shared resources based on patterns of access to shared resources. (A master node for a shared resource governs access by other nodes to the shared resources.) For example, if most of the accesses to a portion of shared data are performed by a particular node, that node is assigned as the master node for that portion of the shared data. This reduces the messaging overhead between nodes but does not eliminate the cost of executing more instructions to acquire a global lock.
Another technique to reduce the cost of acquiring global locks is to use coarse-grain locking. In this scheme, locks are acquired at a higher level of granularity, such as a table or file, instead of a finer level of granularity, such as a row or a disk block. When a lock is acquired at the higher level of granularity, it is implicitly granted for levels of shared data at a finer level of granularity. For example, if a global lock is acquired for an entire table, individual global locks for the rows or blocks for the table are implied and do not have to be acquired, avoiding the cost of obtaining a global lock for each row and block.
The advantage of this technique is that it does not depend on the assignment of a master node. A significant disadvantage, however, is that this technique can lead to false contention. Specifically, if a node needs to modify a row in a table that has been locked by another node in a conflicting mode, that node must relinquish the lock on the table although the two nodes may be accessing different rows or even different blocks.
Another technique to reduce the cost of acquiring global locks is to use hierarchical locking. In this scheme, locks are first acquired at a higher level in the hierarchy, such as a table. If a global lock is acquired at a higher level in the hierarchy, global locks are implicitly granted at the lower level of the hierarchy. When another node subsequently needs to access data in the lower level of the hierarchy, such as a row or a block, in a conflicting mode, the first node de-escalates its lock and acquires locks at the lower level in the hierarchy.
The disadvantage of this technique is that the cost of obtaining a global lock is inflated and shifted to the requesting node whose lock request triggers the de-escalation. To honor the request, work is performed to acquire global locks for all the shared data at the lower level of the hierarchy. This work is performed despite the requesting node having requested a lock on only a small portion of the shared data.
As clearly shown, techniques are needed to reduce the cost of acquiring global locks that avoid the pitfalls attendant to techniques described above for reducing the cost of global locks.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.